Optical fiber networks comprise a plurality of nodes connected together by bundles of optical fibers. Until recently, optical fiber communication technology could support only one wavelength per fiber, so making a connection through a network was a matter of selecting a series of links and particular fibers in the series of links.
Recent improvements in technology have made it possible to transmit multiple carriers of different wavelengths through a single fiber. Current technology should soon provide up to about 80 wavelengths on a single fiber, enabling a single fiber to carry 80 times as much traffic as a single-wavelength fiber. It is predicted that capacity may go as high as 128 to 160 wavelengths.
Thus routing takes on an extra dimension. Not only must a link and a fiber within that link be chosen, but an available wavelength must also be selected. Wavelength changers, which take a signal at one wavelength and convert it to another wavelength, are available, albeit they are complex and expensive.
Various routing algorithms for multiple-wavelength fiber networks have been developed in attempts to make the network operate efficiently. These algorithms are based on the current state of the network. For example, a xe2x80x9cFirst to Fitxe2x80x9d algorithm may choose the path with the lowest available wavelength, or if the path is already determined, pick the lowest available wavelength on that path. A xe2x80x9cMost Usedxe2x80x9d algorithm selects a wavelength that is already used on the most fibers. A random algorithm selects a wavelength randomly in a uniform manner. The xe2x80x9cLeast Loaded Routingxe2x80x9d algorithm selects a wavelength-path, that is, a wavelength and series of links, with the least congested link.
A typical problem which may result from prior algorithms is that the utilization of the particular wavelength-path chosen by the algorithm may remove from availability the only remaining link capable of providing a connection between some other pair of nodes, thereby unnecessarily reducing the availability of the network. To maximize the ability of the network to provide as many connections as possible, the present invention assigns channels such as wavelengths, and paths based, at least in part, on the state of the network after possible assignments. Where current methods look only at the current state of the candidate paths, the present invention tries to leave the network overall in a xe2x80x9cbetterxe2x80x9d or more flexible state.
In accordance with the present invention, candidate channel-paths are allocated to connections in a network, where a candidate channel-path comprises a candidate path and candidate channel along the candidate path, by determining individual effects on the network of selecting candidate channel-paths. These include effects on at least one channel-path, other than a candidate channel-path, which shares a link with the candidate path. Candidate channel-paths are selected based on the determined effects and allocated.
In a preferred embodiment, determination of the effects on the network is based on path capacity. The embodiment can be used where a single connection has been requested, or alternatively, where multiple connections have been requested.
A max-sum embodiment selects candidate channel-paths by first calculating a sum of path capacity-dependent values of a set of paths in the network for each of plural network states resulting from candidate channel-path allocations, and then selecting the candidate channel-paths yielding a maximum sum.
In a preferred embodiment, each path capacity dependent value is a path capacity multiplied by a weight associated with the path. In one alternative, the weight associated with a path p is the inverse of the path capacity of path p prior to allocating channel-paths. In another alternative, the weight for a path p is an inverse of the path capacity of network path p in its empty state with no connections. In yet another alternative, each path capacity dependent value is the path capacity associated with the path, i.e. all weights are 1. In still another embodiment, the weight for a path p is based on a prediction of the future traffic load of path p, for example, an average of past traffic load, or usage, of path
In a preferred embodiment, selecting the candidate channel-paths is based on a difference, for each of plural network states resulting from channel-path allocations, of path-capacities before and after the allocation. Determining the difference comprises determining a count, for each candidate channel-path, of paths in the network whose capacities are decreased by one.
Where the network is a ring network, determining the count for a candidate channel-path further comprises, for each value i between 1 and the number of links n in the candidate channel-path: determining a minimum capacity ki for a first i links of the candidate channel-path; determining a minimum capacity gi for a last i links of the candidate channel-path; determining a first gap value hi(l) equal to a number of links from the first link in candidate channel-path in a first direction to a link with link capacity less than ki; and determining a second gap value hi(r) equal to a number of links from a last link i in a second direction to the first link with link capacity less than gi. Then hi(l), hi(r), the number of links in the candidate channel-path, and the total number of links in the network, are used to calculate the count.
Alternatively, determining the count for a candidate channel-path further comprises, for each candidate channel-path: determining a set of paths such that all paths in the set have a minimum capacity link in common with the candidate path at the candidate channel, and using the size of the set of paths as the count.
A max-min embodiment determines and selects the candidate channel-paths by first determining a minimum path capacity of a set of paths in the network for each possible configuration of candidate channel-path allocations, and then selecting the candidate channel-paths yielding a largest minimum.
The present invention is designed for optical fiber networks, preferably with a plurality of fibers within each link, however it is applicable to other types of networks as well. In the preferred embodiments, channels correspond to wavelengths. However, the present invention is not limited to wavelength channels in optical fiber networks. For example, in alternative embodiments, the network could use time division multiple access (TDMA) where channels correspond to time slots.
The present invention also provides benefits to networks having channel changers, in which case channel-paths can be assigned to hops between channel changers or between channel changers and source or destination nodes.
In a preferred embodiment, multiple channels are available in a single path.
In yet another embodiment, paths are preselected and only candidate channels must be allocated.